#include "bst.h"

Bst *insert(Bst *root, int data) {
    if (root == 0) {
        Bst *newNode = malloc(sizeof(Bst));
        assert(newNode);
        newNode->data = data;
        newNode->left = newNode->right = 0;
        root = newNode;
    } else if (data < root->data) {
        root->left = insert(root->left, data);
    } else {
        root->right = insert(root->right, data);
    }
    return root;
}

bool isInTree(Bst *root, int data) {
    if (root == 0) {
        return false;
    }
    if (data == root->data) {
        return  true;
    } else if (data < root->data) {
        return isInTree(root->left, data);
    } else {
        return isInTree(root->right, data);
    }
}

int getMax(Bst *root) {
    if (root == 0) {
        exit(EXIT_FAILURE);
    }
    if (root->right == 0) {
        return root->data;
    } else {
        return getMax(root->right);
    }
}

int getMin(Bst *root) {
    if (root == 0) {
        exit(EXIT_FAILURE);
    }
    if (root->left == 0) {
        return root->data;
    } else {
        return getMin(root->left);
    }
}

int maxNum(int a, int b) {
    if (a >= b) {
        return a;
    } else {
        return b;
    }
}

int getHeight(Bst *root) {
    if (root == 0) {
        return -1;
    }
    return 1 + maxNum(getHeight(root->left), getHeight(root->right));
}

bool isBst(Bst *root) {
    return isBetween(root, INT_MIN, INT_MAX);
}

bool isBetween(Bst *root, int min, int max) {
    if (root == 0) {
        return true;
    }
    return root->data > min && root->data < max && isBetween(root->left, min, root->data)
        && isBetween(root->right, root->data, max);
}

Bst *delete(Bst *root, int data) {
    if (root == 0) {
        return 0;
    }
    if (data < root->data) {
        root->left = delete(root->left, data);
    } else if (data > root->data) {
        root->right = delete(root->right, data);
    } else {
        if (root->left == 0 && root->right == 0) {
            free(root);
            root = 0;
        } else if (root->right == 0) {
            Bst *tmp = root;
            root = root->left;
            free(tmp);
        } else if (root->left == 0) {
            Bst *tmp = root;
            root = root->right;
            free(tmp);
        } else {
            int newData = getMin(root->right);
            root->data = newData;
            root->right = delete(root->right, newData);
        }
    }
    return root;
}

int getSuccessor(Bst *root, int data) {
    Bst *target = findNode(root, data);
    if (target == 0) {
        return -1;
    }
    if (target->right != 0) {
        return getMin(target->right);
    }
    Bst *successor = 0;
    Bst *ancestor = root;
    while (ancestor != 0) {
        if (data < ancestor->data) {
            successor = ancestor;
            ancestor = ancestor->left;
        } else {
            ancestor = ancestor->right;
        }
    }
    if (successor != 0){
        return successor->data;
    }
    return -1;
}

Bst *findNode(Bst *root, int data) {
    if (root == 0 || data == root->data) {
        return root;
    }
    if (data < root->data) {
        return findNode(root->left, data);
    } else {
        return findNode(root->right, data);
    }
}

void printValues(Bst *root) {
    if (root == 0) {
        return;
    }
    printValues(root->left);
    printf("%d\n", root->data);
    printValues(root->right);
}

int getNodeCount(Bst *root) {
    if (root == 0) {
        return 0;
    }
    return 1 + getNodeCount(root->left) + getNodeCount(root->right);
}
